Searching অ্যালগরিদম: Linear Search, Binary Search

Searching অ্যালগরিদম হল ডেটা সংগ্রহের মধ্যে নির্দিষ্ট একটি মান খুঁজে বের করার প্রক্রিয়া। দুইটি জনপ্রিয় সার্চিং অ্যালগরিদম হল Linear Search এবং Binary Search। এই দুটি অ্যালগরিদমের মধ্যে বিভিন্নতা আছে, এবং তাদের কার্যকারিতা ও ব্যবহার ক্ষেত্র ভিন্ন।

1. Linear Search

Linear Search (লাইনিয়ার সার্চ) হল সবচেয়ে মৌলিক সার্চিং অ্যালগরিদম। এটি একটি তালিকার প্রতিটি উপাদানকে sequentially পরীক্ষা করে এবং নির্দিষ্ট মানটি খুঁজে বের করে।

বৈশিষ্ট্য:

• টাইম কমপ্লেক্সিটি: O(n), যেখানে n হল উপাদানের সংখ্যা। (সবচেয়ে খারাপ ক্ষেত্রে)
• স্পেস কমপ্লেক্সিটি: O(1) (ইন-প্লেস সার্চ)।

উদাহরণ (C++):

#include <iostream>
#include <vector>

int linearSearch(const std::vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i; // টার্গেট পাওয়া গেলে ইনডেক্স রিটার্ন করুন
        }
    }
    return -1; // টার্গেট পাওয়া না গেলে -1 রিটার্ন করুন
}

int main() {
    std::vector<int> arr = {5, 3, 8, 6, 2, 7};
    int target = 6;
    
    int result = linearSearch(arr, target);
    if (result != -1) {
        std::cout << "Element found at index: " << result << std::endl;
    } else {
        std::cout << "Element not found." << std::endl;
    }
    
    return 0;
}

2. Binary Search

Binary Search (বাইনারি সার্চ) একটি কার্যকরী সার্চিং অ্যালগরিদম, যা শুধুমাত্র সাজানো তালিকায় কাজ করে। এটি তালিকার মধ্যবর্তী উপাদানটি পরীক্ষা করে এবং নির্ধারণ করে যে টার্গেট মানটি মধ্যবর্তী মানের চেয়ে ছোট বা বড়। এরপর এটি পুনরায় সেই সাব-অংশে সার্চ চালায়।

বৈশিষ্ট্য:

• টাইম কমপ্লেক্সিটি: O(log n) (যেহেতু এটি প্রতি পদক্ষেপে তালিকার আকার অর্ধেক করে)।
• স্পেস কমপ্লেক্সিটি: O(1) (ইন-প্লেস সার্চ)।

উদাহরণ (C++):

#include <iostream>
#include <vector>
#include <algorithm> // sort() এর জন্য

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // মধ্যবর্তী ইনডেক্স

        if (arr[mid] == target) {
            return mid; // টার্গেট পাওয়া গেলে ইনডেক্স রিটার্ন করুন
        }
        else if (arr[mid] < target) {
            left = mid + 1; // ডান দিকে চলুন
        }
        else {
            right = mid - 1; // বাম দিকে চলুন
        }
    }
    return -1; // টার্গেট পাওয়া না গেলে -1 রিটার্ন করুন
}

int main() {
    std::vector<int> arr = {2, 3, 5, 6, 7, 8}; // সাজানো তালিকা
    int target = 5;

    int result = binarySearch(arr, target);
    if (result != -1) {
        std::cout << "Element found at index: " << result << std::endl;
    } else {
        std::cout << "Element not found." << std::endl;
    }

    return 0;
}

সারাংশ

Linear Search:

• সহজ এবং সরল অ্যালগরিদম।
• কোনো সাজানোর প্রয়োজন নেই, কিন্তু এর টাইম কমপ্লেক্সিটি O(n), যা বড় ডেটাসেটে কার্যকর নয়।

Binary Search:

• সাজানো তালিকার জন্য একটি কার্যকরী অ্যালগরিদম।
• এর টাইম কমপ্লেক্সিটি O(log n), যা বৃহৎ ডেটাসেটের জন্য অনেক দ্রুত।
• তবে এটি কাজ করার জন্য তালিকাটি অবশ্যই সাজানো হতে হবে।

এই দুটি সার্চিং অ্যালগরিদম বিভিন্ন পরিস্থিতিতে ব্যবহৃত হয় এবং সঠিক অ্যালগরিদম নির্বাচন প্রোগ্রামের কার্যকারিতা বাড়াতে সাহায্য করে।